/*
 * Copyright (c) 1995, 1996, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package sun.misc;

import java.util.Dictionary;
import java.util.Enumeration;
import java.util.NoSuchElementException;

/**
 * Caches the collision list.
 */
@SuppressWarnings("deprecation")
class CacheEntry extends Ref {
	int hash;
	Object key;
	CacheEntry next;

	public Object reconstitute() {
		return null;
	}
}

/**
 * The Cache class. Maps keys to values. Any object can be used as a key and/or
 * value. This is very similar to the Hashtable class, except that after putting
 * an object into the Cache, it is not guaranteed that a subsequent get will
 * return it. The Cache will automatically remove entries if memory is getting
 * tight and if the entry is not referenced from outside the Cache.
 * <p>
 * 
 * To sucessfully store and retrieve objects from a hash table the object used
 * as the key must implement the hashCode() and equals() methods.
 * <p>
 * 
 * This example creates a Cache of numbers. It uses the names of the numbers as
 * keys:
 * 
 * <pre>
 * Cache numbers = new Cache();
 * numbers.put(&quot;one&quot;, new Integer(1));
 * numbers.put(&quot;two&quot;, new Integer(1));
 * numbers.put(&quot;three&quot;, new Integer(1));
 * </pre>
 * 
 * To retrieve a number use:
 * 
 * <pre>
 * Integer n = (Integer) numbers.get(&quot;two&quot;);
 * if (n != null) {
 * 	System.out.println(&quot;two = &quot; + n);
 * }
 * </pre>
 * 
 * @see java.lang.Object#hashCode
 * @see java.lang.Object#equals
 * @see sun.misc.Ref
 */
@SuppressWarnings("rawtypes")
public class Cache extends Dictionary {
	/**
	 * The hash table data.
	 */
	private CacheEntry table[];

	/**
	 * The total number of entries in the hash table.
	 */
	private int count;

	/**
	 * Rehashes the table when count exceeds this threshold.
	 */
	private int threshold;

	/**
	 * The load factor for the hashtable.
	 */
	private float loadFactor;

	private void init(int initialCapacity, float loadFactor) {
		if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
			throw new IllegalArgumentException();
		}
		this.loadFactor = loadFactor;
		table = new CacheEntry[initialCapacity];
		threshold = (int) (initialCapacity * loadFactor);
	}

	/**
	 * Constructs a new, empty Cache with the specified initial capacity and the
	 * specified load factor.
	 * 
	 * @param initialCapacity
	 *            the initial number of buckets
	 * @param loadFactor
	 *            a number between 0.0 and 1.0, it defines the threshold for
	 *            rehashing the Cache into a bigger one.
	 * @exception IllegalArgumentException
	 *                If the initial capacity is less than or equal to zero.
	 * @exception IllegalArgumentException
	 *                If the load factor is less than or equal to zero.
	 */
	public Cache(int initialCapacity, float loadFactor) {
		init(initialCapacity, loadFactor);
	}

	/**
	 * Constructs a new, empty Cache with the specified initial capacity.
	 * 
	 * @param initialCapacity
	 *            the initial number of buckets
	 */
	public Cache(int initialCapacity) {
		init(initialCapacity, 0.75f);
	}

	/**
	 * Constructs a new, empty Cache. A default capacity and load factor is
	 * used. Note that the Cache will automatically grow when it gets full.
	 */
	public Cache() {
		try {
			init(101, 0.75f);
		} catch (IllegalArgumentException ex) {
			// This should never happen
			throw new Error("panic");
		}
	}

	/**
	 * Returns the number of elements contained within the Cache.
	 */
	public int size() {
		return count;
	}

	/**
	 * Returns true if the Cache contains no elements.
	 */
	public boolean isEmpty() {
		return count == 0;
	}

	/**
	 * Returns an enumeration of the Cache's keys.
	 * 
	 * @see Cache#elements
	 * @see Enumeration
	 */
	public synchronized Enumeration keys() {
		return new CacheEnumerator(table, true);
	}

	/**
	 * Returns an enumeration of the elements. Use the Enumeration methods on
	 * the returned object to fetch the elements sequentially.
	 * 
	 * @see Cache#keys
	 * @see Enumeration
	 */
	public synchronized Enumeration elements() {
		return new CacheEnumerator(table, false);
	}

	/**
	 * Gets the object associated with the specified key in the Cache.
	 * 
	 * @param key
	 *            the key in the hash table
	 * @returns the element for the key or null if the key is not defined in the
	 *          hash table.
	 * @see Cache#put
	 */
	@SuppressWarnings("deprecation")
	public synchronized Object get(Object key) {
		CacheEntry tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		for (CacheEntry e = tab[index]; e != null; e = e.next) {
			if ((e.hash == hash) && e.key.equals(key)) {
				return e.check();
			}
		}
		return null;
	}

	/**
	 * Rehashes the contents of the table into a bigger table. This is method is
	 * called automatically when the Cache's size exceeds the threshold.
	 */
	@SuppressWarnings("deprecation")
	protected void rehash() {
		int oldCapacity = table.length;
		CacheEntry oldTable[] = table;

		int newCapacity = oldCapacity * 2 + 1;
		CacheEntry newTable[] = new CacheEntry[newCapacity];

		threshold = (int) (newCapacity * loadFactor);
		table = newTable;

		// System.out.println("rehash old=" + oldCapacity + ", new=" +
		// newCapacity + ", thresh=" + threshold + ", count=" + count);

		for (int i = oldCapacity; i-- > 0;) {
			for (CacheEntry old = oldTable[i]; old != null;) {
				CacheEntry e = old;
				old = old.next;
				if (e.check() != null) {
					int index = (e.hash & 0x7FFFFFFF) % newCapacity;
					e.next = newTable[index];
					newTable[index] = e;
				} else
					count--; /* remove entries that have disappeared */
			}
		}
	}

	/**
	 * Puts the specified element into the Cache, using the specified key. The
	 * element may be retrieved by doing a get() with the same key. The key and
	 * the element cannot be null.
	 * 
	 * @param key
	 *            the specified hashtable key
	 * @param value
	 *            the specified element
	 * @return the old value of the key, or null if it did not have one.
	 * @exception NullPointerException
	 *                If the value of the specified element is null.
	 * @see Cache#get
	 */
	@SuppressWarnings("deprecation")
	public synchronized Object put(Object key, Object value) {
		// Make sure the value is not null
		if (value == null) {
			throw new NullPointerException();
		}
		// Makes sure the key is not already in the cache.
		CacheEntry tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		CacheEntry ne = null;
		for (CacheEntry e = tab[index]; e != null; e = e.next) {
			if ((e.hash == hash) && e.key.equals(key)) {
				Object old = e.check();
				e.setThing(value);
				return old;
			} else if (e.check() == null)
				ne = e; /* reuse old flushed value */
		}

		if (count >= threshold) {
			// Rehash the table if the threshold is exceeded
			rehash();
			return put(key, value);
		}
		// Creates the new entry.
		if (ne == null) {
			ne = new CacheEntry();
			ne.next = tab[index];
			tab[index] = ne;
			count++;
		}
		ne.hash = hash;
		ne.key = key;
		ne.setThing(value);
		return null;
	}

	/**
	 * Removes the element corresponding to the key. Does nothing if the key is
	 * not present.
	 * 
	 * @param key
	 *            the key that needs to be removed
	 * @return the value of key, or null if the key was not found.
	 */
	@SuppressWarnings("deprecation")
	public synchronized Object remove(Object key) {
		CacheEntry tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		for (CacheEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
			if ((e.hash == hash) && e.key.equals(key)) {
				if (prev != null) {
					prev.next = e.next;
				} else {
					tab[index] = e.next;
				}
				count--;
				return e.check();
			}
		}
		return null;
	}
}

/**
 * A Cache enumerator class. This class should remain opaque to the client. It
 * will use the Enumeration interface.
 */
@SuppressWarnings("rawtypes")
class CacheEnumerator implements Enumeration {
	boolean keys;
	int index;
	CacheEntry table[];
	CacheEntry entry;

	CacheEnumerator(CacheEntry table[], boolean keys) {
		this.table = table;
		this.keys = keys;
		this.index = table.length;
	}

	@SuppressWarnings("deprecation")
	public boolean hasMoreElements() {
		while (index >= 0) {
			while (entry != null)
				if (entry.check() != null)
					return true;
				else
					entry = entry.next;
			while (--index >= 0 && (entry = table[index]) == null)
				;
		}
		return false;
	}

	@SuppressWarnings("deprecation")
	public Object nextElement() {
		while (index >= 0) {
			if (entry == null)
				while (--index >= 0 && (entry = table[index]) == null)
					;
			if (entry != null) {
				CacheEntry e = entry;
				entry = e.next;
				if (e.check() != null)
					return keys ? e.key : e.check();
			}
		}
		throw new NoSuchElementException("CacheEnumerator");
	}

}
